//2009/07/19 22:16:53
#include<iostream>
#include<vector>
#include<string>

using namespace std;

class FourBlocks
{
public:
    //Don't forget to CLEAR VECTOR at the beginning!!!
    int maxScore(vector<string> grid)
    {
        int n = grid.size();
        int m = grid[0].size();
        for (int i=0; i< 2048; i++)
        {
            for (int j=0; j<26*12; j++)
            {
                dp[j][i] = -1<<20;
            }
        }
        dp[0][0] = 0;
		int mask = (1<<(n+1))-1;
		for(int i=0; i<m*n; i++)
		{
			for(int j=0; j < 1<<(n+1); j++)
			{
				int x = i%n, y = i/n; // Row:x, Column:y.
				dp[i+1][(j*2)&mask] >? = dp[i][j];
				if(x!=0 && ((j>>n)&1)) continue;
				if((j>>(n-1)) & 1) continue;
				if((j>>(n-2)) & 1) continue;
				if(j & 1) continue;
				if(x!=n-1 && y!=m-1 && grid[x][y]=='.' && grid[x][y+1]=='.'&&grid[x+1][y]=='.' && grid[x+1][y+1]=='.')
					dp[i+1][(j*2+1)&mask] >? = dp[i][j] +4;
			}
		}
		int mx = 0;
		for(int i=0; i<2048; i++)
		{
			mx >?= dp[n*m][i];
		}
		return m*n + mx*3;
    }

private:
    int dp[12*26][2048];
};
//A copy from wywcgs;
